package xin.javashare.sort;

/**
 *计数排序，k=max-min+1,c=new int[k]
 */
public class CountSort {
    /**
     *  使用辅助数组b
     * @param a
     * @return
     */
    public static void countSort(int[] a) {
        int b[] = new int[a.length];
        int max = a[0], min = a[0];
        for (int i : a) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        //这里k的大小是要排序的数组中，元素大小的极值差+1
        int k = max - min + 1;//考点，优化过的地方，减小了数组c的大小
        int c[] = new int[k];
        //c[i]存放a[i]-min出现的次数
        for (int i = 0; i < a.length; ++i) {
            c[a[i] - min] += 1;
        }
        // 累加,c[i]存放的是小于等于a[i]-min的数的个数
        for (int i = 1; i < c.length; ++i) {
            c[i] = c[i] + c[i - 1];
        }
        // 使用辅助数组b
        for (int i = a.length - 1; i >= 0; --i) {
            b[--c[a[i] - min]] = a[i];//按存取的方式取出c的元素
        }
        for(int i = 0; i < b.length; ++i) {
            a[i] = b[i];
        }
    }

    /**
     * 不使用辅助数组，原地排序，
     * 借助a[i]出现的次数，若c[i]>0, 则i + min就是a中的一个值，且在原数组中的位置为idx
     * @param a
     */
    public static void countSort2(int[] a) {
        int min = a[0];
        int max = a[0];
        int n = a.length;
        for (int anA : a) {
            if (anA > max) {
                max = anA;
            }
            if (anA < min) {
                min = anA;
            }
        }

        int k = max - min + 1;
        int[] c = new int[k];
        for (int anA : a) {
            c[anA - min]++;
        }

        int idx = 0;
        for (int i = 0; i < k; ++i) {
            // 依次取完
            while(c[i] > 0) {
                a[idx++] = i + min; // 注意这里
                c[i]--;
            }
        }

    }

    public static void main(String[] args) {
        int[] list = {2, 3, 2, 5, 10, 1, -2, 3, 14, 12};
        countSort2(list);

        for (int aList : list) {
            System.out.print(aList + " ");
        }
    }
}
